import java.util.Arrays;

/**
二分查找：
 Params：a-待查找的升序数组
        target-带查找的目标值
 Return：找到则返回索引
        找不到返回 -1
 */
public class Binary_Search {
    public static void main(String[] args) {
        int[] arr = { 12, 25, 36, 47, 51,51, 63, 76, 87, 97};
        int target = 51;
//        int result1 = BinarySearch.binarySearch(arr, target);
//        System.out.println(result1);
//        int result2 = BinarySearch_Alternative.binarySearch(arr, target);
//        System.out.println(result2);
        Binary2 b = new Binary2();
        int a = b.binary_rightmost2(arr, target);
        System.out.println(a);
    }
}
class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int i = 0, j = arr.length - 1; //确定索引
        /*
        现在我想查找一个元素，已知循环次数为L次。
        如果元素在最左边，则执行L次
        如果元素在最右边，则执行2*L次
        所以查找起来并不是平衡的
         */
        while (i <= j) {
            int mid = (i+j)>>>1;
            if (target<arr[mid]) {//目标在左边
                j = mid-1;
            }else if (arr[mid]<target) {//目标在右边
                i = mid+1;
            }else{
                return mid;  //找到了，返回其索引
            }
        }//判断元素是否在有序的一维数组当中

        return -1;
    }//左闭右闭
    public static int binary3(int[] arr, int target) {
        int i = 0, j = arr.length;
        while (1<j-i) {// j - i 表示所有待查的元素
            int mid = (i+j)>>>1;
            if (target < arr[mid]) {
                    j = mid;
            }else{
                    i = mid;
            }
        }
        if (target == arr[i]) {
            return i;
        }else{
            return -1;
        }
    }
    /*
    对于次算法：
    1. 左闭右开的区间，i 指向的可能是目标，而 j 指向的不是目标
    2. 不在循环内找出，等范围内只剩i时，退出循环，在循环外比较a[i]与target
    3. 循环内的平均比较次数减少了
    4. 时间复杂度θ(log(n))
     */
}
/*
 问题1： 为什么是 i <= j 意味着区间有未比较的元素，而不是 i<j?
       i,j 它们指向的元素也会参与比较：当i和j指向同一个元素时，就会将其漏掉，没有进行比较
 问题2：  （i+j）/2 有没有问题?
        其实是问题的，当我的最右边的索引是整数值上的最大值时，当我继续进行(i+j)
        java会将其视为负数，为什么呢？因为Java会将二进制的最高位会看成符号位，将其判断负数
        会导致两个正数相加结果为负数
 */
class BinarySearch_Alternative {
    public static int binarySearch(int[] arr, int target) {
        int i = 0, j = arr.length ; //对于这个二分查找的修改版，将j设置为一个边界，它一定不会是查找的目标，只是一个边界
        while (i < j) {//i指向的元素会是查找的目标，而j只是作为一个边界，一定不会是查找的目标！
            int mid = (i+j)>>>1;
            if (arr[mid] < target) {
                i = mid + 1;
            }else if (arr[mid] > target) {
                j = mid; //任然将此处作为一个边界，它指向的一定不是查找的值
            }else{
                return mid;
            }
        }

        return -1;
    }
}//左闭右开

//如何衡量一个算法的好坏?
/**
 * 线性查找
 * Params: a-带查找的升序数组（可以不是有序数组）
 *         target-待查找的目标值
 * Return:
 *         找到则返回索引
 *         找不到则返回-1
 */
class linearSearch {
public static int linearSearch(int [] arr, int target) {
    for(int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
        return -1;
    }
}
//为了简化，1. 只分析算法的最坏执行情况
//	      2.假设每行语句执行时间一样(t)
/*
针对线性查找的代码，假设数据个数为n个
        int i = 0          1
        i < arr.length     n+1
        i++                n
        arr[i] == target   n
        return -1          1
        最终代码执行次数： 3*n +3
 */
//针对于上述基础版的二分查找：
/*
    对于二分查找，右边找不到的效果更差
    int i = 0, j = arr.length - 1；     2
    return -1                           1
     元素个数               循环次数
     4-7                    3           floor(log_2(4))+1
     8-15                   4           floor(log_2(8))+1
     16-31                  5           floor(log_2(16))+1
     32-63                  6           floor(log_2(32))+1
     ...                    ...
     规律： 循环次数 = floor(log_2(n))+1
     假设元素个数是n，循环次数是L
     i <= j                             L+1
     int mid = (i+j)>>>1                L
     arr[mid] < target                  L
     arr[mid] > target)                 L
     j = mid - 1                        L
     最终执行次数： (floor(log_2(n))+1)*5 +4
*/

/**
 * 二分查找 (找到最左边的索引）
 * Params：a-待查找的升序数组
 *         target-带查找的目标值
 * Return：找到则返回最靠左索引
 *         找不到返回 -1
 */
class Binary1{
    public static int binary_leftmost1(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        int candidate = -1;
        while (i <= j) {
            int mid = (i+j)>>>1;
            if (target<arr[mid]) {
                j = mid-1;
            }else if (arr[mid]<target) {
                i = mid+1;
            }else{
                candidate = mid;
                j = mid-1;
            }
        }
        return candidate;
    }

    /**
     * 二分查找 (找到最左边的索引）
     *  Params：a-待查找的升序数组
     *           target-带查找的目标值
     *  Return：返回 >= target的最左索引
     */
    public static int binary_leftmost2(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int mid = (i+j)>>>1;
            if (target<=arr[mid]) {
                j = mid-1;
            }else {
                i = mid+1;
            }
        }
        return i;
    }
}
/**
 * 二分查找 (找到最右边的索引）
 * Params：a-待查找的升序数组
 *         target-带查找的目标值
 * Return：找到则返回最靠右索引
 *         找不到返回 -1
 */
class Binary2{
    public static int binary_rightmost1(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        int candidate = -1;
        while (i <= j) {
            int mid = (i+j)>>>1;
            if (target<arr[mid]) {
                j = mid-1;
            }else if (arr[mid]<target) {
                i = mid+1;
            }else{
                candidate = mid;
                i = mid + 1;
            }
        }
        return candidate;
    }
    /**
     * 二分查找 (找到最左边的索引）
     *  Params：a-待查找的升序数组
     *           target-带查找的目标值
     *  Return：返回 <= target的最右索引
     */
    public static int binary_rightmost2(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int mid = (i+j)>>>1;
            if (target<arr[mid]) {
                j = mid-1;
            }else {
                i = mid+1;
            }
        }
        return i -1;
    }
}